package com.tql.day_02;
/*并列排序
    先排序左边的，在排序右边的，最后整合排序
    比较左右俩个区域，比较对应位置的数字大小，开辟新的空间，存放小的数值
    如果左边越界，复制右边剩余的到开辟的空间，左边同理
 */
public class Test2 {
    public static void main(String[] args) {
        int []arr={2,3,1,4,0,8};
        int[] process1 = process(arr, 0, arr.length - 1);
        for(int i:process1){
            System.out.println(i);
        }
    }
    public static int [] process(int []arr,int L,int R){
        if (L==R){
            return null;
        }
        int mid=L+((R-L)>>1);
        process(arr,L,mid);
        process(arr,mid+1,R);

       return  mearge(arr,L,mid,R);
    }
    public static int [] mearge(int []arr,int L,int mid,int R){
        //开辟空间
        int []help=new int [R-L+1];
        int i=0;
        int p1=L;
        int p2=mid+1;
        //实现数组有序复制，未出现数组越界
        while(p1<=mid&&p2<=R){
            help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        //数组溢出处理
        while(p1<=mid){
            help[i++]=arr[p1++];
        }
        while(p2<=R){
            help[i++]=arr[p2++];
        }
        //赋值到原来的数组，交换已经有序的数据
        for (int j = 0; j<help.length; j++) {
            arr[L + j] = help[j];
        }
        return arr;
    }
}

